{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "# Genetic algorithms\n",
    "\n",
    "Genetic algorithms explore the possible solutions using a method inspired in natural selection. The fundamental components of natural selection are the ability to encode information related to the characteristics of individuals into chromosomes and genes, allowing individuals to mix this information in pairs (by *breeding*) so that the next generation inherits features of both parents, also introducing some mutations so that these new individuals may also have unique features. Then, selection will select only the fittest individuals to produce the next generation. Genetic Algorithms can be used to solve a wide range of problems, including Mixed Integer Programming.\n",
    "\n",
    "![genetic algorithm](img/genetic_algorithm.png){width=50%}\n",
    "\n",
    "Moreover, genetic algorithms work as follows:\n",
    "\n",
    "- **Initialisation:** A random function generates an initial population. The *chromosome* is a set of features or genes that represents a solution of a problem. Each individual in the initial population has a different chromosome.\n",
    "\n",
    "- **Fitness Function:** The objective function is evaluated for each individual to determine which are the fittest individuals in the population. It determines the *fitness score* of each individual. The highest fitness score represents the fittest score of the generation\n",
    "\n",
    "- **Selection Function:**  The individuals with the highest fitness score are selected and paired according to their fitness score\n",
    "\n",
    "- **Crossover Function:** For every pair, the offspring is created assigning genes from both parents\n",
    "\n",
    "- **Mutation Function:** A random function changes some genes in the offspring with low probability\n",
    "\n",
    "- **Termination:** If the algorithm converges at a given generation, new offspring will have no differential features and will not improve the fittest score, so we can terminate the search\n"
   ],
   "metadata": {
    "collapsed": false
   }
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}